package com.xiaoyu.backtracking;

import java.util.*;

/**
 * @program: DS_and_A
 * @description: 全排序
 *
 * 给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
 *  输入：nums = [1,2,3]
 *  输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
 *
 *  即排列中的A33
 *
 *  对于回溯过程使用的变量,我们有两种办法：
 *         1.每做完一种尝试，都把实验材料恢复成做上一个实验之前的样子，只有这样做出的对比才有意义；
 *         2.每一次尝试都使用同样的新的材料做实验。
 *
 *  由于回溯算法的时间复杂度很高，因此在遍历的时候，
 *  如果能够提前知道这一条分支不能搜索到满意的结果，就可以提前结束，这一步操作称为 剪枝。
 *
 *  剪枝:
 *         回溯算法会应用「剪枝」技巧达到以加快搜索速度。
 *         有些时候，需要做一些预处理工作（例如排序）才能达到剪枝的目的。
 *         预处理工作虽然也消耗时间，但能够剪枝节约的时间更多；
 *
 *         提示：剪枝是一种技巧，通常需要根据不同问题场景采用不同的剪枝策略，需要在做题的过程中不断总结。
 *
 *         由于回溯问题本身时间复杂度就很高，所以能用空间换时间就尽量使用空间。
 *
 * 回溯总结:
 * 做题的时候，建议 先画树形图 ，画图能帮助我们想清楚递归结构，想清楚如何剪枝。
 * 拿题目中的示例，想一想人是怎么做的，一般这样下来，这棵递归树都不难画出。
 *
 * 在画图的过程中思考清楚：
 *
 * 分支如何产生；
 * 题目需要的解在哪里？是在叶子结点、还是在非叶子结点、还是在从跟结点到叶子结点的路径？
 * 哪些搜索会产生不需要的解的？例如：产生重复是什么原因，
 * 如果在浅层就知道这个分支不能产生需要的结果，应该提前剪枝，剪枝的条件是什么，代码怎么写？
 *
 * @author: YuWenYi
 * @create: 2021-05-21 09:40
 **/
public class Permute_46 {

    public List<List<Integer>> permute(int[] nums) {
        int len = nums.length;
        List<List<Integer>> res = new ArrayList<>();
        if (len == 0){
            return res;
        }
        //用于判断数组中的数字是否被使用过
        boolean[] used = new boolean[len];

        List<Integer> path = new ArrayList<>();
        dfs(nums, len, 0, path, used, res);
        //Set<List<Integer>> set = new HashSet<>(res);
        return res;
    }

    private void dfs(int[] nums, int len, int depth,
                     List<Integer> path, boolean[] used,
                     List<List<Integer>> res) {
        //因为每次递归都会在结果中添加一个数字
        //因此如果递归的深度和数组的长度一样长了,那么就说明找到了我们需要的结果
        if (len == depth){
            //不能直接: res.add(path),否则结果将会全是[],回溯将状态全部变成了最原始的状态
            //这里必须要将结果复制一份,因为由于回溯,参数值传递的原因,这个path数组的值是会变化的!
            res.add(new ArrayList<>(path));
            //递归触底反弹
            return;
        }

        for (int i = 0; i < len; i++) {
            //如果第i个元素还未被使用过,那么就可以直接使用它
            if (!used[i]){
                //添加变量和修改used数组!
                path.add(nums[i]);
                used[i] = true;
                //开始递归
                System.out.println("--递归前的path:"+path);
                dfs(nums, len, depth + 1,path,used,res);

                //递归结束,此时已经获取了一次结果,现在我们需要将状态还原,即进行回溯!!
                //删除最后面的那个元素,类似栈,后入先出
                path.remove(path.size() - 1);
                //重新将其改为未使用
                used[i] = false;
                System.out.println("递归后的path:"+path);
            }
        }
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3};
        Permute_46 solution = new Permute_46();
        List<List<Integer>> lists = solution.permute(nums);
        System.out.println(lists);
    }

}
